package com.loie.datacenter.util;

public class KnapsackWithSelection {
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};  // 物品重量
        int[] values = {3, 4, 5, 6};   // 物品价值
        int capacity = 8;              // 背包容量

        // 计算最大价值并获取DP数组
        int[][] dp = calculateKnapsack(weights, values, capacity);
        int maxValue = dp[weights.length][capacity];

        // 回溯找出选中的物品
        boolean[] selected = findSelectedItems(dp, weights, capacity);

        // 打印结果
        System.out.println("背包最大容量: " + capacity);
        System.out.println("物品信息:");
        for (int i = 0; i < weights.length; i++) {
            System.out.printf("物品%d: 重量=%d, 价值=%d%n", i+1, weights[i], values[i]);
        }
        System.out.println("\n最大价值为: " + maxValue);
        System.out.println("选中的物品:");
        for (int i = 0; i < selected.length; i++) {
            if (selected[i]) {
                System.out.printf("物品%d (重量=%d, 价值=%d)%n",
                        i+1, weights[i], values[i]);
            }
        }
    }

    /**
     * 计算背包问题的DP数组，并打印填充过程
     */
    public static int[][] calculateKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        System.out.println("===== DP数组填充过程 =====");
        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            System.out.printf("\n处理第%d个物品 (重量=%d, 价值=%d):\n",
                    i, weights[i-1], values[i-1]);
            // 遍历每个容量
            for (int j = 1; j <= capacity; j++) {
                // 情况1：当前物品重量大于背包容量，无法放入
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                    System.out.printf("容量=%d: 物品%d太重，不放入，价值=%d\n",
                            j, i, dp[i][j]);
                } else {
                    // 情况2：可以放入，取两种选择的最大值
                    int notTake = dp[i - 1][j];  // 不放入当前物品
                    int take = values[i - 1] + dp[i - 1][j - weights[i - 1]];  // 放入当前物品
                    dp[i][j] = Math.max(notTake, take);

                    if (take > notTake) {
                        System.out.printf("容量=%d: 放入物品%d，价值=%d (物品价值%d + 剩余容量%d的价值%d)\n",
                                j, i, dp[i][j], values[i-1], j-weights[i-1], dp[i-1][j-weights[i-1]]);
                    } else {
                        System.out.printf("容量=%d: 不放入物品%d，价值=%d (保持前%d个物品的最优解)\n",
                                j, i, dp[i][j], i-1);
                    }
                }
                for (int i1 = 1; i1 <= n; i1++){
                    for (int j1 = 1; j1 <= capacity; j1++)
                        System.out.println("dp["+i1+"]["+j1+"]="+dp[i1][j1]);
                }

            }
        }
        return dp;
    }

    /**
     * 回溯找出选中的物品
     */
    public static boolean[] findSelectedItems(int[][] dp, int[] weights, int capacity) {
        int n = weights.length;
        boolean[] selected = new boolean[n];
        int remainingCapacity = capacity;

        // 从最后一个物品开始回溯
        for (int i = n; i > 0; i--) {
            // 如果当前物品的价值不等于上一行同容量的价值，说明选中了该物品
            if (dp[i][remainingCapacity] != dp[i - 1][remainingCapacity]) {
                selected[i - 1] = true;
                remainingCapacity -= weights[i - 1];  // 减去当前物品的重量
            }
        }
        return selected;
    }
}

